// 数组中第k个最大的数
let findKthLargest = function (nums, k) {
    nums.sort((a, b) => b - a).slice(0, k);
    return nums[k - 1]
}

let quickSort = (arr) => {
    quick(arr, 0, arr.length - 1)
}
let quick = (arr, left, right) => {
    let index;
    if (left < right) {
        index = partition(arr, left, right);
        if (left < index - 1) {
            quick(arr, left, index - 1)
        }
        if (index < right) {
            quick(arr, index, right)
        }
    }
}
let partition = (arr, left, right) => {
    var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
        i = left;
    j = right;

    while (i <= j) {
        while (arr[i] < datum) {
            i++
        }
        while (arr[j] > datum) {
            j--
        }
        if (i <= j) {
            swap(arr, i, j)
            i += 1;
            j -= 1
        }
    }
    return i
}
let swap = (arr, i, j) => {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp
}